package lc.q5400_q5450;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。
 *
 * 请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。
 *
 */
public class Q5414 {



    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        favoriteCompanies.forEach(strings -> strings.sort(String::compareTo));
        List<Integer> results = new ArrayList<>();
        // 可以维护一个数组表示已经比较过的值，省略掉
        for (int i = 0; i < favoriteCompanies.size(); i++) {
            final List<String> s = favoriteCompanies.get(i);
            boolean contain = false;
            for (int j = 0; j < favoriteCompanies.size(); j++) {
                if (i != j && isContain(favoriteCompanies.get(j), s)) {
                    contain = true;
                    break;
                }
            }
            if (!contain) {
                results.add(i);
            }
        }
        return results;
    }

    public boolean isContain(List<String> arr1, List<String> arr2) {
        if (arr1.size() < arr2.size()) {
            return false;
        }
        // 因为排序好的
        final int i1 = arr1.size() - arr2.size();
        int j = 0;
        for (int i = 0; i < arr2.size(); i++) {
            while (!arr2.get(i).equals(arr1.get(j))) {
                j ++;
                if (i1 < (j - i)) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        final Q5414 q5414 = new Q5414();
        final String[][] strings = {
                {"leetcode", "google", "facebook"},
                {"google", "microsoft"},
                {"google", "facebook"},
                {"google"},
                {"amazon"}
        };
        List<List<String>> params = new ArrayList<>();
        for (String[] string : strings) {
            params.add(new ArrayList<>(Arrays.asList(string)));
        }
        final List<Integer> list = q5414.peopleIndexes(params);
        System.out.println(list);
    }

}
